package org.algorithm.Sort;

public class QuickSort2 {


    private void QuickSort3Way2(int []array,int left,int right){
        if (left>right){
            return;
        }

        int piv =array[left];

        int lt = left;
        int gt = right+1;
        int curr =left+1;

        while (curr<gt){
            if (array[curr]<piv){
                swap(array,curr,lt);
                lt++;
                curr++;
            }else if (array[curr]>piv){
                gt--;
                swap(array,curr,gt);
            }else {
                curr++;
            }
        }
        QuickSort3Way2(array,left,lt-1);
        QuickSort3Way2(array,gt,right);
    }
    private void QuickSort3Way(int []array,int left,int right){

        if (left>=right){
            return;
        }

        int piv = array[left];

        int lt = left;
        int gt = right+1;
        int curr = left+1;

        while (curr<gt){

            if (array[curr]<piv){
                swap(array,curr,lt);
                lt++;
                curr++;
            }else if (piv<array[curr]){
                gt--;
                swap(array,curr,gt);
            }else {
                curr++;
            }

        }

        QuickSort3Way(array,left,lt-1);
        QuickSort3Way(array,gt,right);
    }

    private void swap(int [] array,int n1,int n2){
        if (n1==n2){
            return;
        }
        int temp = array[n1];
        array[n1]=array[n2];
        array[n2]=temp;
    }

    public static void main(String[] args) {
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};

        QuickSort2 quickSort2 = new QuickSort2();
        quickSort2.QuickSort3Way(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

}
